11.2 距離不超過 3 倍的 Baswana-Sen Spanner

如果我們把近似最短距離的要求再度放寬，比方說找出一個子圖 H，使得圖 H 上任兩點之間的最短距離，都不超過圖 G 的 3 倍。在印度理工學院念博士班的 Surender Baswana 與他的指導教授 Sandeep Sen 發表了一篇非常有效率的演算法，在線性時間內找出一個子圖 H 滿足上述條件，而且這個子圖的邊數至多只有期望 n^1.5 條（在最壞情況下達到理論下界），跟前一節提及的 +2 Spanner 數量相近。

要怎麼做呢？演算法如下：

1. 首先讓每個點以 1/n^{0.5} 的機率被選入集合 S 作為叢集中心(Cluster Center)。
2. 對於所有沒被選中的點 v，如果他與其中一個 S 的點 x 相鄰，就把 v 指派給 x。如果與多個 S 內的點相鄰，就隨意挑選一個 S 中的點 x 來指派，並且將 (v, x) 這條邊加入 H。經過這步驟以後，絕大部分的點都已經被指派進入某個叢集了。
3. 如果一個點沒有被指派給任何叢集(也就是說它不與所有 S 內的點相鄰)，就把它所有的相鄰邊都加入 H。
4. 對於每個點 v (無論有或沒有選中)，我們將它的鄰居們根據叢集分門別類，對於每個相鄰的叢集，挑選一條邊加入 H。
5. 然後我們就做完啦！

時間複雜度是線性的：每一個步驟，都會讓每個點、每條邊被考慮至多 2 次(邊有兩個方向)。
圖 H 內的期望邊數有 n^1.5 條，因為首先，集合 S 的大小是期望 n^0.5 個點。因此，第四步驟所加入 H 的邊數是期望 n * n^0.5 = n^1.5 條。然後，第二步驟增加的邊數為 O(n)。接著，如果一個點沒有被指派進入任何一個叢集，那麼它的期望鄰居數量是 n^0.5 個點，所以第三步驟期望加入的總邊數也是 n^1.5 條。

最後，需要稍微感覺一下為什麼這個演算法保證了至多 3 倍。事實上，如果這是一個無向無權圖，那麼距離其實是 “2倍+1”。如果是有權重的圖，我們可以修改第二步驟(指派給最接近的點)、以及第四步驟(每個叢集選最接近的那個鄰居加邊)，這樣能保證 “3倍”。

考慮一條沒有被加入 H 的邊 (u, v)，顯然 u 和 v 都屬於某個叢集(否則這條邊就會被第三步驟抓住)。不妨假設 v 的叢集中心是 Cv。那根據第四步驟，在我們考慮 u 的時候，必定連了一條 u → Cv 所在叢集的某個點 w (而此時 w 必定不是 v)。於是，我們有一條路 u → w → Cv → v，距離保證是至多 3 倍。

考慮任何一條圖 G 上的最短路徑 s ⇝ t，這條路徑上在圖 H 所有缺失的邊都能以上述方法在 3 條邊之內搞定。因此這個圖 H 的確是近似最短路徑的 3-Spanner。

值得注意的是，這個演算法並沒有辦法幫助我們快速地找出近似 APSP。若要對每一個點都做一次 BFS/Dijkstra，那麼時間複雜度仍然是期望的 n^2.5。